package arithmetic2;

import utils.PrintUtil;

/**
 * @author macpro
 * @date 2019-08-10
 * @function
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 *
 * Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
 *
 * Example:
 *
 * Input:
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * Output: 1->1->2->3->4->4->5->6
 *
 */
public class T_023_MergeKSorketdList {
    public static void main(String[] args) {


        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(4);
        ListNode node4 = new ListNode(5);

        node1.next=node2;
        node2.next=node4;

        ListNode node11 = new ListNode(1);
        ListNode node22 = new ListNode(3);
        ListNode node44 = new ListNode(4);
        node11.next=node22;
        node22.next=node44;

        ListNode node222 = new ListNode(2);
        ListNode node666= new ListNode(6);

        node222.next = node666;

//        ListNode temp = node222;
//        System.out.println(node222 +" "+ temp );
//        temp = temp.next;
//        System.out.println(node222 +" "+ temp);
//        System.out.println(node222.val+" "+temp.val);

        PrintUtil.print(mergeKLists(new ListNode[]{node1,node11,node222}));
    }


    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode(0);
        System.out.println(head);
        ListNode temp = head;
        sortNode(temp,lists);
        return head.next;
    }

    private static int sortNode(ListNode temp, ListNode[] lists ) {


        int[] minNode = getMinNode(lists);

        if (minNode[0]==-1){//都是null

            return -1;
        }else {//
            temp.next = lists[minNode[1]];
            lists[minNode[1]]=lists[minNode[1]].next;
            temp = temp.next;
            sortNode(temp,lists);
        }
        return 0;
    }

    private static int[] getMinNode(ListNode[] lists ) {

        int minRes =Integer.MAX_VALUE;
        int minIndex = 0;
        int isNull = -1;
        for (int i = 0; i < lists.length; i++) {
            ListNode node = lists[i];
            if (node != null) {
                isNull = 0;
                if (node.val<= minRes){
                    minRes = node.val;
                    minIndex = i;
                }
            }
        }

        return new int[]{isNull,minIndex};

    }
}
